541. Reverse String II

1. Question

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2kbut greater than or equal to k characters, then reverse the first k characters and left the other as original.

2. Examples

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

3. Constraints

• 1 <= s.length <= 10⁴
• s consists of only lowercase English letters.
• 1 <= k <= 10⁴

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-string-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

暴力

class Solution {
    public String reverseStr(String s, int k) {

        StringBuffer sb = new StringBuffer();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (i % (2 * k) == k) {
                while (!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
            }
            if (i % (2 * k) < k) {
                stack.push(s.charAt(i));
            } else if (i % (2 * k) >= k) {
                sb.append(s.charAt(i));
            }

            if (i == s.length() - 1) {
                while (!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
            }

        }
        return sb.toString();

    }
}

模拟

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}